package com.example.system.class05;

/**
 * @Date 2022/7/23
 * @Created by Jonathan
 */
public class Code02_SmallSum {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 2, 4, 9, 7, 8, 4};
        System.out.println(getSmallSum(arr));
        int[] arr1 = new int[]{3, 1, 2, 4, 9, 7, 8, 4};
        System.out.println(comparator(arr1));
    }

    public static int getSmallSum(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid)
                + process(arr, mid + 1, right)
                + merge(arr, left, mid, right);
    }

    private static int merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int l = left;
        int r = mid + 1;
        int index = 0;
        int ans = 0;
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                ans += arr[l] * (right - r + 1);  // 右边有几个数比当前的数大 那么当前的数就要乘以几
                help[index++] = arr[l++];
            } else {
                help[index++] = arr[r++];
            }
        }
        //
        while (l <= mid) {
            help[index++] = arr[l++];
        }
        while (r <= right) {
            help[index++] = arr[r++];
        }
        // 将原来的拷贝回去
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }

    // for test
    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (arr[j] < arr[i]) {
                    ans += arr[j];
                }
            }
        }
        return ans;
    }
}
